package sum;

import java.util.Stack;
/**
 * 题目：
 * 数组 arr = [2,3,5,7,9]，输出任意组合，可以重复选，输出所有和是 13 的组合：
 * 0 - [2, 2, 2, 2, 2, 3] - 13
 * 1 - [2, 2, 2, 2, 5] - 13
 * 2 - [2, 2, 2, 7] - 13
 * 3 - [2, 2, 3, 3, 3] - 13
 * 4 - [2, 2, 9] - 13
 * 5 - [2, 3, 3, 5] - 13
 * 6 - [3, 3, 7] - 13
 * 7 - [3, 5, 5] - 13
 */
/**
 * @author eii
 * @time 2020/10/27 7:26 下午
 */
public class NSum {
    static int res = 13;
    static int idx = 0;
    public static void main(String[] args) {
        int[] arr = {2, 3, 5, 7, 9};
        Stack<Integer> resStack = new Stack();
        traceback(arr, 0, 0,resStack);
    }

    /**
     *
     * @param arr
     * @param s
     * @param sum
     * @param resStack
     */
    public static void traceback(int[] arr, int s,int sum,Stack<Integer> resStack){
        for (int i = s; i < arr.length; i++) {
            int cs = sum + arr[i];
            if(cs > res){
                break;
            }
            resStack.push(arr[i]);
            if(cs == res){
                System.out.println(idx++ + " - " + resStack + " - " + cs);
                resStack.pop();
                break;
            }
            traceback(arr,i,cs,resStack);
            resStack.pop();
        }
    }
}

